package com.example.bbbb.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-12-15
 * Time: 14:29
 */


public class Sort {


    /**
     * 冒泡排序
     * 稳定
     * O(n^2)
     */
    public static void bubbleSort(int[] arr) {
        // 排序轮数
        int n = arr.length - 1;
        for (int i = 0; i < n; i++) {
            boolean flag = true;
            for (int j = 0; j < n - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag) {
                return;
            }
        }
    }


    public static void qsort(int[] arr) {
        qsortImpl(arr, 0, arr.length - 1);
    }

    /**
     * 三分快排，能够进一步解决二分快排超时的问题
     * 不稳定
     * O(NlogN)
     */
    private static void qsortImpl(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        // 随机选定中间值
        int midVal = arr[new Random().nextInt(r - l + 1) + l];
        // 将区间分成三段
        // [val < mid) [mid] [val > mid)
        int left = l - 1, right = r + 1;// 便于操作边界
        int i = l;// 遍历的起始位置
        while (i < right) {
            if (arr[i] < midVal) {
                swap(arr, ++left, i++);// 搬到最左边，i 移动
            } else if (arr[i] == midVal) {
                i++;
            } else {
                swap(arr, i, --right);// 搬到最右边，i 位置不动（为下一轮循环重新判断刚交换的值）
            }
        }
        // 结果
        // [l, left] [midVal] [right, r]
        // 左递归
        qsortImpl(arr, l, left);
        // 右递归
        qsortImpl(arr, right, r);
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    /**
     * 选择排序，不断选出最小的和最前面的指针交换
     * 不稳定
     * O(n)
     */
    public static void selectSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int index = i;
            int indexVal = arr[i];
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < indexVal) {
                    index = j;
                    indexVal = arr[j];
                }
            }
            if (index != i) {
                int tmp = arr[i];
                arr[i] = indexVal;
                arr[index] = tmp;
            }
        }
    }


    /**
     * 插入排序，不断地将较小值插入到前面
     * 稳定
     * O(N^2)
     */
    public static void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int indexVal = arr[i];// 要插入的值
            int index = i - 1;// 要插入的位置
            while (index >= 0 && indexVal < arr[index]) {// 选择合适的位置，数组往后挪一个位置
                arr[index + 1] = arr[index];
                index--;
            }
            // 插入到指定的位置后面 i + 1
            arr[index + 1] = indexVal;
        }
    }


    /**
     * 希尔排序，是对插入排序的优化（即先让部分元素有序，将大数和小数分布与左右）
     * 不稳定
     * O(NlogN)
     */
    public static void shellSort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {// 步长可以自定义，一般是 /2
            // 将插入排序的代码中的 1 替换为 gap 即可
            for (int i = gap; i < n; i++) {
                int index = i - gap;
                int indexVal = arr[i];
                while (index >= 0 && indexVal < arr[index]) {
                    arr[index + gap] = arr[index];
                    index -= gap;
                }
                arr[index + gap] = indexVal;
            }
        }
    }



    public static int[] tmp;// 给归并排序使用

    public static void mergeSort(int[] arr) {
        tmp = new int[arr.length];
        mergeSortImpl(arr, 0, arr.length - 1);
    }


    /**
     * 归并排序（递归实现）
     *
     */
    private static void mergeSortImpl(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 中间值
        int mid = left + (right - left) / 2;
        // 左
        mergeSortImpl(arr, left, mid);
        // 右
        mergeSortImpl(arr, mid + 1, right);

        int cur1 = left, cur2 = mid + 1;// 左起始点，右起始点
        int i = 0;// tmp 的起始点
        while (cur1 <= mid && cur2 <= right) {
            if (arr[cur1] < arr[cur2]) {
                tmp[i++] = arr[cur1++];
            } else {
                tmp[i++] = arr[cur2++];
            }
        }
        // 判断是否到末尾
        while (cur1 <= mid) {
            tmp[i++] = arr[cur1++];
        }
        while (cur2 <= right) {
            tmp[i++] = arr[cur2++];
        }
        // 拷贝回原数组
        System.arraycopy(tmp, 0, arr, left, right - left + 1);
    }


    /**
     * 归并排序（非递归）
     * 稳定
     * O(NlogN)
     */
    public static void mergeSortNor(int[] arr) {
        int n = arr.length;
        tmp = new int[n];
        int gap = 1;// 步长
        while (gap < n) {
            for (int i = 0; i < n; i += gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if (mid >= n) {
                    mid = n - 1;
                }
                if (right >= n) {
                    right = n - 1;
                }
                merge(arr, left, mid, right);
            }
            gap *= 2;
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (arr[cur1] < arr[cur2]) {
                tmp[i++] = arr[cur1++];
            } else {
                tmp[i++] = arr[cur2++];
            }
        }
        while (cur1 <= mid) {
            tmp[i++] = arr[cur1++];
        }
        while (cur2 <= right) {
            tmp[i++] = arr[cur2++];
        }
        System.arraycopy(tmp, 0, arr, left, right - left + 1);
    }


    /**
     * 堆排序
     * O(NlogN)
     * 不稳定
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;
        // 从下到上先调整为大根堆
        // i 的值从 0 开始，为每层根节点的下标
        for (int i = n / 2 - 1; i >= 0; i--) {
            shiftDown(arr, i, n);
        }
        for (int i = n - 1; i >= 0; i--) {
            // 将最大值（即arr [0] 调整到数组最后
            int tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            // 此时最大的元素已经调整完成
            // 忽略掉最后一个元素，再次调整为大根堆
            shiftDown(arr, 0, i);
        }

    }


    /**
     * 调整子树为大根堆
     * @param arr
     * @param parent 根节点下标
     * @param size 数组大小
     */
    private static void shiftDown(int[] arr, int parent, int size) {
        int child = parent * 2 + 1;
        while (child < size) {
            // 选出较大的子节点
            if (child + 1 < size && arr[child] < arr[child + 1]) {
                child++;
            }
            if (arr[child] > arr[parent]) {// 子大于父
                // 交换最大值
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
                // 调整交换后的子树
                parent = child;
                child = parent * 2 + 1;
            } else {// 子小于父，已经是大根堆了
                break;
            }
        }
    }


    /**
     * 计数排序
     * O(N + k)，k 为临时数组的大小
     * 稳定
     */
    public static void countSort(int[] arr) {
        int min = arr[0];
        int max = arr[0];
        // 选出最大值和最小值
        for (int i = 1; i < arr.length; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }
        // 可能有负数，所以需要这样处理
        int n = max - min + 1;
        int[] count = new int[n];
        // 遍历原数组，统计各个元素出现的次数
        for (int val : arr) {
            // 将元素映射为下标
            int index = val - min;
            // 统计数量
            count[index]++;
        }
        // 将元素按照个数填回原数组
        int index = 0;
        for (int i = 0; i < n; i++) {
            while (count[i] > 0) {// 有几个值填回去几个
                int val = i + min;
                arr[index++] = val;
                count[i]--;
            }
        }
    }


    /**
     * 桶排序
     * O(NlogN)
     * 稳定
     */
    public static void bucketSort(int[] arr) {
        // 根据《算法》中描述每个桶的大小在 5~10 之间性能最优。
        bucketSortImpl(arr, new Random().nextInt(5, 11));
    }




    private static void bucketSortImpl(int[] arr, int bucketSize) {
        if (arr.length == 0) {
            return;
        }
        int min = arr[0];
        int max = arr[0];
        for (int val : arr) {
            min = Math.min(min, val);
            max = Math.max(max, val);
        }
        // 算出桶的个数
        int bucketCount = (max - min) / bucketSize + 1;
        // 桶内的元素个数都开到最大
        int[][] buckets = new int[bucketCount][arr.length];
        // 统计每个桶内元素的个数
        int[] nums = new int[bucketCount];
        for (int val : arr) {
            // 将每个元素映射到各个桶里
            int dest = (val - min) / bucketSize;
            // 更新桶内元素个数
            buckets[dest][nums[dest]++] = val;
        }
        int index = 0;
        for (int i = 0; i < bucketCount; i++) {
            if (nums[i] != 0) {
                // 排序每个桶里的元素
                myInsertSort(buckets[i], nums[i]);
                // 将排序好的元素放回原数组
                for (int j = 0; j < nums[i]; j++) {
                    arr[index++] = buckets[i][j];
                }
            }
        }
    }

    private static void myInsertSort(int[] arr, int len) {
        for (int i = 1; i < len; i++) {
            int index = i - 1;
            int indexVal = arr[i];
            while (index >= 0 && indexVal < arr[index]) {
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = indexVal;
        }
    }


    /**
     * 基数排序
     * O(n*k)
     * 稳定
     * @param arr
     */
    public static void radixSort(int[] arr) {
        int min = arr[0];
        int max = arr[0];
        for (int val : arr) {
            min = Math.min(min, val);
            max = Math.max(max, val);
        }
        // 解决负数的问题
        int offset = Math.abs(min);
        for (int i = 0; i < arr.length; i++) {
            arr[i] += offset;
        }
        // 更新最大值
        max += offset;
        // 确定位数
        int maxDigits = (int) (Math.log10(max) + 1);
        // 0-9 十位
        int[][] buckets = new int[10][arr.length];
        // 记录桶内的元素个数
        int[] nums = new int[10];
        // 开始根据每位分割数组
        for (int digit = 0; digit < maxDigits; digit++) {
            int tmp = (int) Math.pow(10, digit);
            for (int val : arr) {
                // 取出每一位作为下标
                int index = (val / tmp) % 10;
                buckets[index][nums[index]++] = val;
            }
            // 每轮分配完毕后，需要将桶内的元素，按顺序放回
            int k = 0;
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < nums[i]; j++) {
                    arr[k++] = buckets[i][j];
                }
                // 将记录数组个数归零
                nums[i] = 0;
            }
        }
        // 将 offset 减回
        for (int i = 0; i < arr.length; i++) {
            arr[i] -= offset;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2, 1, 3, -9, 4, -3, 7};
        int[] arr1 = new int[]{2, 1};
//        bubbleSort(arr1);
//        qsort(arr);
//        selectSort(arr);
//        selectSort(arr1);
//        insertSort(arr);
//        insertSort(arr1);
//        shellSort(arr);
//        shellSort(arr1);
//        mergeSort(arr);
//        mergeSort(arr1);
//        mergeSortNor(arr);
//        mergeSortNor(arr1);
//        heapSort(arr);
//        heapSort(arr1);
//        countSort(arr);
//        countSort(arr1);
//        bucketSort(arr);
//        bucketSort(arr1);
        radixSort(arr);
        radixSort(arr1);

        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr1));
    }
}
